#define TRUE 1
#define FALSE 0
#define INVALID -1
#define NULL 0
#define total_instruction 320
#define total_vp 32
#define clear_period 50

typedef struct {
    int pn;
    int pfn;
    int counter;
    int time;
} pl_type;

pl_type pl[total_vp];

typedef struct pfc_struct {
    int pn;
    int pfn;
    struct pfc_struct *next;
} pfc_type;

pfc_type pfc[total_vp], *freepf_head, *busypf_head, *busypf_tail;
int diseffect, a[total_instruction];
int page[total_instruction], offset[total_instruction];
int initialize(int);
int FIFO(int);
int LRU(int);
int LFU(int);
int NUR(int);
int OPT(int);

int main() {
    int s, i, j;
    srand(10 * getpid());
    s = (float)319*rand()/32767/32767/2+1;
    for(i = 0; i < total_instruction; i += 4) {
        if( s < 0 || s > 319 ) {
            printf("When i==%d,Error,s==%d\n", i, s);
            exit(0);
        }
        a[i] = s;
        a[i + 1] = a[i] + 1;
        a[i + 2] = (float)a[i]*rand( )/32767/32767/2;
        a[i + 3] = a[i + 2] + 1;
        s = (float)(318-a[i+2])*rand()/32767/32767/2+a[i+2]+2;
        if((a[i + 2] > 318) || (s > 319))
            printf("a[%d+2],a number which is :%d and s==%d\n", i, a[i + 2], s);
    }
    for (i = 0; i < total_instruction; i++) {
        page[i] = a[i] / 10;
        offset[i] = a[i] % 10;
    }
	for (i=4;i<=32;i++){
		printf("---%2d page frames ---\n", i);
		LRU(i);
	}
    return 0;
}

int initialize(int total_pf) {
    int i;
    diseffect = 0;
    for(i = 0; i < total_vp; i++) {
        pl[i].pfn = INVALID;
        pl[i].counter = 0;
        pl[i].time = -1;
    }
    for(i = 0; i < total_pf - 1; i++) {
        pfc[i].next = &pfc[i + 1];
        pfc[i].pfn = i;
    }
    pfc[total_pf - 1].next = NULL;
    pfc[total_pf - 1].pfn = total_pf - 1;
    freepf_head = &pfc[0];
    return 0;
}

int LRU(int total_pf){
	int min,minj,i,j,present_time;
	initialize(total_pf);
	present_time=0;
	for(i=0;i<total_instruction;i++){
		if(pl[page[i]].pfn==INVALID){
			diseffect++;
			if(freepf_head==NULL){
				min=32767;
				for(j=0;j<total_vp;j++){
					if(min>pl[j].time&&pl[j].pfn!=INVALID){
						min=pl[j].time;
						minj=j;
					}
				}
				freepf_head=&pfc[pl[minj].pfn];
				pl[minj].pfn=INVALID;
				pl[minj].time=0;
				freepf_head->next=NULL;
			}
			pl[page[i]].pfn=freepf_head->pfn;
			pl[page[i]].time=present_time;
			freepf_head=freepf_head->next;
		}
		else{
			pl[page[i]].time=present_time;
			present_time++;
		}
	}
	printf("LRU:%6.4f\n", 1-(float)diseffect/320);
	return 0;
}
